package leetcode.动态规划;

import org.junit.Test;

/**
 * @author :songyaozhang
 * @date :Created 2021/8/16 15:50
 * @description :https://leetcode-cn.com/problems/house-robber/
 */
public class 打家劫舍 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
    }

    class Solution {
        public int rob(int[] nums) {
            int n = nums.length;
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            int[] dp = new int[n];
            dp[0] = nums[0];
            dp[1] = Math.max(nums[0], nums[1]);
            for (int i = 2; i < n; i++) {
                dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
            }
            return dp[n - 1];
        }
    }
}
